The present invention relates to a Viterbi decoder apparatus and to a Viterbi decoding method using survivor vector traceback methods.
In communications systems, data transmitted are often corrupted by noise or other distortions. As a result, the data obtained at the receiving station may not be an accurate replica of the transmitted data. To increase the reliability of the data received, redundancy in the form of error correction and error checking codes is often added to the transmitted signal to allow error correction by the receiving unit. The addition of the redundant information before transmission is known as a forward error correction (“FEC”) technique. The redundant data is typically applied in an encoding block of the transmission circuit. A typical data communication system encodes the data before transmission, transmits the data through a noisy medium where the data may be corrupted, and processes the received encoded data in a Viterbi decoder where the encoded data is converted to its original format. As detailed further below, a Viterbi decoder moves forward through a sequence of received encoded data, determining a most likely path with respect to the transmitted codes and then performs a traceback on the most likely path to provide decoded data.
An encoder, an example of which is shown in FIG. 3, may produce several successive output bits which are correlated with one input bit. This correlation gives the coded data its error correcting capabilities. Shift registers and combinational logic which performs modulo-2 addition may be used, for example, to encode the data. The rectangular boxes labeled D0, D1, and D2 each represent one element of a serial shift register. The contents of the shift registers are shifted from left to right. The input X1 is used to load the shift register with a new input data bit as well as load the modulo-2 adders 302 and 304. The outputs from the modulo-2 adders are multiplexed to generate multiple coded digits of output for every binary digit (bit) that enters the encoder. For the encoder shown, the constraint length L is 3, which is defined as the number of bits used to encode the data.
Conceptually, each set of bits of encoded information may be represented by a state. The possible transitions from one state to a next state are limited. Each of these possible transitions can be shown graphically in a state diagram as depicted in FIG. 1A or in a similar manner by a transition table (FIG. 1B), or trellis diagrams (FIGS. 2A, 2B). Each possible transition from one state to a next state is defined as a branch. In the encoder, the state is represented by the most significant L−1 message bits moved into the encoder. The number of possible states for the encoder can be represented by the expression 2(L-1) where L is the constraint length. Thus, when the constraint length is 3 as shown in FIG. 3, four states are possible. The convolutional encoder shown encodes at a rate of ½, meaning that the encoder outputs 2 data bits for every received input bit. As shown, a limited number of transitions to next state are possible from the current state, depending upon whether the input bit is a “0” or a “1”.
All possible combinations of the initial state and the input digit are used to determine the next state and the output bits. Each of the four states, “00”, “01”, “10”, and “11” are shown by the boxes 102–108. Transitions between states are represented by the connecting arrows between the rectangular boxes. The notation next to the arrows indicate the input bits followed by the output bits involved in the transition. For example, in transitioning from state “10”, notation 110 indicates an input bit of “0” will result in the output bits “10” and a next state of “01” as indicated by box 106. The section of the trellis diagram depicted in FIG. 2 relates to a ½ convolutional encoder. The four possible states (00, 01, 10, and 11) are labeled alongside the left margin of the trellis. The four states labeled along the right margin represent the next state. Two lines or branches enter each next state and are typically referred to as the upper and lower branches. For example, as shown, state 10 has an upper branch feeding it from state 00 and a lower branch feeding it from state 01. The codeword, i.e., the group of output bits associated with the transition between states, is marked along the connecting branch line. For example, for the branch transitioning from state 01 to next state 10, notation 203 along the branch indicates an input of “1” that will result in an output codeword of “00” as the transition between the two states occurs.
The encoded transmitted data, after passing through a noisy channel, may be decoded at the receiver using a Viterbi algorithm. A Viterbi decoder, described in the overview which follows, is a maximum likelihood decoder providing forward error correction through the use of a Viterbi algorithm. Generally, in the decoding process, a Viterbi decoder works forward through the received sequence, and assigns a “cost” or “distance” to each state in that section of the trellis diagram, for each received word of the sequence. This cost is used to determine which previous state in the trellis was most likely to branch to the current state. The survivor vector (survivor) gives the indication as to which previous state was the most likely source, for example when there are two possible source states, whether the upper or lower source branch was the most likely previous state. More than 2 source states are possible and as known to those of skill in the art, the number of possible states depends on the encoding rate k (e.g. 2^k possible branches produce 1 survivor). The decoder then performs a traceback by working backward through the trellis, using the survivors to determine what the most likely path through the trellis was. The decoded bit is determined by the most likely source (i.e. oldest state in the trellis). The path is defined sequence of interconnected branches.
A trellis diagram, such as shown in FIG. 2B, is used to determine a most likely path, i.e. a path having a distance nearest to a transmitted series of encoded bits. The trellis diagram depicts the paths stretching out from the states at an initial time instant, with subsequent time instants arranged in the horizontal direction. Thus, the trellis diagram may be used to show the time arrangement of the states. The trellis depth of a trellis diagram represents the number of sections in the diagram. For example, the trellis depth for the Viterbi trellis shown in FIG. 2B is 5.
Any state and time may be represented in the Viterbi trellis diagram by a node, such as node 222 representing state 1 at time t=3. The various times are represented along the horizontal axis. In order for the Viterbi decoding circuit to determine a most likely path from the received encoded data, for each node an accumulated metric is typically determined. The lines connecting the nodes or states are identified as branches. For each branch from a state, a branch metric is determined. One way of defining the branch metric is the Hamming distance between the received codeword and the branch codeword, which is the number of differences between the codeword (or bits) received by the communications system and the branch codeword such as example codeword 224. The branch codeword represents the output bits generated when the transition between the current state and the next state occurs. Other measures, such as the square of the distance, may be used as alternatives to determine the branch metric.
For each node representing a next state, the new accumulated path metric is the sum of the branch metric and the accumulated metric for the source of the branch. In the example shown in FIG. 2B, two branches enter each node. Only one of the branches will survive. The surviving branch is determined by comparing, for each of the two branches, the sum of the source node's accumulated path metric and the branch metric for that branch. The surviving branch may be represented by the lower of the two sums or the higher of the sums, depending on the method. For example, in situations where the Hamming distance is not measured but rather the correlation between the received value and branch codeword is used to determine the branch metric, the highest value is selected. If the sums for the branches are equal, any branch may be randomly selected as the survivor. The sum for the surviving branch then becomes the accumulated path metric for the destination node (next state). These steps are repeated for each state in each section of the trellis diagram until the end of the Viterbi trellis diagram is reached. Typically, an add-compare-select (“ACS”) circuit determines the surviving branch in this forward movement through the Viterbi diagram.
In order to generate the decoded bits, a traceback is performed from the final state, often by initially selecting as the starting point the final state with the minimum accumulated metric. In the traceback, a minimized path is selected from the final state to the initial state (represented by the first or leftmost trellis section). In this reverse direction, the path from each node travels along the survivor branches. In the reverse direction only one surviving path or branch leaves each node, i.e. the survivor branch. The traceback therefore provides a funneling action (in the reverse direction) which directs the traceback along the minimized path. After the calculation of the path metrics in the forward direction, every state has one surviving branch terminating at it. This intermediate state may, however, have more than one surviving branch leaving it. But, given a sufficient number of steps in the traceback, all possible paths are expected to converge to one path. The number of steps or the trellis depth is typically selected to be at least 5*L, where L is the constraint length of the code, but may be as high as 15*L for punctured codes. Typically, only the oldest message bit within the Viterbi trellis diagram is decoded, i.e. the output codeword corresponding to the traceback path in the first or leftmost section of the trellis diagram. The contents of the Viterbi trellis diagram may then be shifted by one code trellis position to the left to vacate a position for the next pair of encoded digits received from the communications channel. This process continues until all bits have been decoded.
In order to implement the Viterbi decoder in hardware, a large number of storage registers are typically used. Given a trellis depth of 35 for decoding, for example, it can be seen that the hardware required by a conventional implementation may exceed the capacity of many devices, such as programmable logic devices or alternatively require the selection of high capacity devices at an increased cost. Moreover, each time a bit is decoded using conventional methods, a complete traceback of the trellis diagram is typically required. The resulting problems include extensive hardware requirements, considerable time in performing the computations, or a combination of these problems. While reducing the traceback depth can present considerable savings in computational time and hardware requirements, such reductions can introduce inaccuracies in the decoded data. What is needed is an implementation that will efficiently permit Viterbi decoding to be performed using limited hardware such as might be available from a single layer in a programmable logic device (“PLD”) or to permit high speed decoding without sacrificing the accuracy attainable using current traceback depths.